This invention relates to pattern recognition systems, and more specifically, to systems employing neural computation to detect preselected sequences in time-varying input signals.
Neural networds have been described by J. J. Hopfield in "Neurons With Graded Response Have Collective Computational Properties Like Those of Two-state Neurons"; Proc. Natl. Sci., USA Vol. 81, pp. 3088-3092; and by J. J. Hopfield and D. W. Tank in "`Neural` Computation of Decisions in Optimization Problems", Biological Cybernetics, Vol. 52, 1985 pp. 141-152; as well as in U.S. patent application Ser. No. 693,479 filed on behalf of J. J. Hopfield of January 2, 1985, and U.S. patent application Ser. No. 795,789 filed on behalf of J. J. Hopfield and D. W. Tank on November 7, 1985.
Basically, a neural network is a highly parallel computational circuit comprising a plurality of amplifers, with each of the amplifiers feeding back its output signal to itself and all of the other amplifiers or chosen other amplifiers through conductance T.sub.ij. The T.sub.ij conductances (where T.sub.ij denotes the conductance between the output of amplifier j and the input of amplifier i) and the associated connections can be thought of as comprising a connection network which has one output signal set and two input signal sets. The output signal set is applied to the amplifier inputs, one of the input signal sets is derived from the amplifier outputs, and the other input signal set is responsive to input stimuli applied to the neural network. As shown in the prior art, one can explicitly specify the values of the T.sub.ij conductances to achieve predetermined results, such as reaching different specified output states of the amplifier in response to different ranges of input stimuli. Also as described in the prior art, an input interconnection network may be interposed between the input stimuli and the second set of inputs of the feedback network. The input interconnection network, which comprises a feed-forward arrangement, converts the expected input signals to corresponding signals that drive the feedback network and the amplifiers. There is no time dependence, however, in this interconnection network.
The arrangement described can be employed to perform many tasks, and we described, by way of example in our 795,789 patent application, its use as an A/D converter. However, not all tasks can be performed with this arrangement alone, and recognition of patterns in time-dependent signals is one such task.
Recognizing patterns in time-dependent signals is an important task that we perform effortlessly in our everyday life. For example, the tasks of recognizing individual spoken phonemes, isolated spoken words in a continuous stream of speech are rapidly accomplished by a person who understands the language being spoken. Similarly, in a movie, if a person is replaced by a pattern of a few dots representing parts of the body, and the person is moving, people who see only the moving dots can immediately identify the dynamic pattern as "a person moving", in spite of complete inability to recognize a "person" from a stationary pattern of the dots (e.g., a single frame of such a movie).
The use of networks to recognize patterns in some classes of continuous input signals has been employed in various contexts. Most of these applications, however, deal with predetermined sequences of input signals and require that the sequence searched for appear exactly as expected, lest it be determined that the sequence is not there at all. There is no room in most systems for concept of "mostly present". The reason for this sensitivity (or rigidity) is that responding to an input sequence that is only close to the expected one is a much more difficult problem to solve. Still, some work has been done in this area. For example, in Neural Theroy and Modeling, ed. R. F. Reis (Stanford University Press, Stanford, Ca.), pp. 105-137, use is described of bandpass filters constructed from simple networks of three or four formal neurons having different time delays. The arrangement described permits recognizing some elementary signal patterns. More recently, a temporal associative memory has been described by K. Fukushima (1973) Kybernetic Vol. 12, pp. 58-63. The network functions by mapping the previous states along a spatial gradient using a set of discrete time delays (shift register). At each clock cycle, the pattern of activity projects the network into the next state in the sequence, using connections that code for all known sequential projections in the same way that associative networks code for all known memories.
These prior art techniques fail for the general pattern recognition case, where the input signal is continuous so that the beginning of the searched-for sequence is not known, and its duration is variable. Also in the general case, the searched-for sequence is often distorted in the data stream because of missing or extraneous signal portions, and because of time warp. A signal containing a sequence is time warped when the relative durations of the components making up the searched-for sequence are different from the expected relative durations.
By way of example, the general pattern recognition problem is illustrated by two sequences, in which each letter symbol represents a particular momentary stimulus state, and the time duration of the stimulus states is represented by letter repetitions. The first sequence (the sound of the word "series") represents the searched-for stimulus sequence, and the second sequence is the data in which a distorted version of the first sequence is embedded in a continuous steam ("this series sounds"). ##STR1## The pattern recognition task is to recognize the first sequence in the second data stream.
Although real situations will generally have continuous time and continuous patterns to deal with, the difficulty of the task can be quite easily understood and appreciated from the above discrete example. Difficulties include (1) where to start the comparison (word-break problem), and (2) given a starting point, different examples of the sequence may be distorted both in time (time warp problem) and in form (missing or extraneous signals).
It is the object of this invention to provide means for more effectively recognizing preselected sequences in a time-dependent signal. It is another object of this invention to provide a simple technique for constructing robust networks for detecting sequences in a time-dependent signal that contains form and time warp distortions.